# 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
#  说明：每次只能向下或者向右移动一步。
#
#  示例 1：
# 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
# 输出：7
# 解释：因为路径 1→3→1→1→1 的总和最小。
#
#  示例 2：
# 输入：grid = [[1,2,3],[4,5,6]]
# 输出：12
from typing import List


class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        """
        动态规划
        和 LeetCode62类似
        要到达(i, j) 必须先到(i - 1, j)或者(i, j - 1)
        dp[i][j]表示从起点到(i, j)的最小路径和
        则 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        :param grid:
        :return:
        """
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]  # dp[i][j] 表示从起点(0, 0)到 (i. j) 的最短路径
        for i in range(m):
            dp[i][0] = (dp[i - 1][0] if i > 0 else 0) + grid[i][0]
        for j in range(1, n):
            dp[0][j] = (dp[0][j - 1] if j > 0 else 0) + grid[0][j]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        return dp[-1][-1]


if __name__ == "__main__":
    grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
    grid = [[1, 2, 3], [4, 5, 6]]
    print(Solution().minPathSum(grid))
